1. Field of the Invention
The present invention relates to a normalization method, a multi-dimensional interpolation method, and an apparatus.
2. Description of the Related Art
Color Reproduction Between Input and Output Devices
In recent years, scanners, video cameras, and the like have prevailed as input devices. Also, various color printers using an ink-jet system, dye sublimation system, electrophotographic system, and the like have prevailed as output devices. In general, these color input and output devices respectively have unique color spaces. For this reason, even when a color image scanned by an arbitrary scanner is transferred to and printed by a color printer intact, the colors of the printed color image rarely match those of the original color image scanned by the scanner.
In order to solve such problems associated with color reproducibility between devices for color images and the like, processing (to be referred to as “color space conversion” hereinafter) for converting a color space of an input device into that of an output device is required. For this purpose, the input and output devices normally incorporate a color space conversion function so as to improve the color reproduction capability between the input and output devices.
Note that the color space conversion indicates a series of entire image processes such as input γ (gamma) correction, luminance-density conversion, masking, black generation, UCR, output γ correction, and the like, or only some processes of them in some cases.
As a color space conversion method, digital image signals of three colors of an input device are simultaneously referred to and are converted into digital image signals of three or four colors of an output device.
The three colors of the input device indicate, e.g., the colors red, blue, and green (the term “RGB” will be used hereinafter to refer to these colors collectively). The three colors of the output device indicate, e.g., the colors cyan, magenta, and yellow (the term “CMY” will be used hereinafter to refer to these colors collectively). The four colors of the output device indicate, e.g., the colors cyan, magenta, yellow, and black (the term “CMYK” will be used hereinafter to refer to these colors collectively). In case of a copying machine of an electrophotographic system, since the engine characteristics of a printer change along with an elapse of running hours, periodic calibration is required. For this reason, in such case, conversion from the four colors (e.g., “CMYK”) of the output device into the four colors (e.g., “CMYK”) of the output device is also required.
Overview of Color Space Conversion Method
As a means for implementing the color space conversion, a method of storing conversion results in a memory in the form of a lookup table (to be abbreviated as “LUT” hereinafter), and outputting conversion results from that LUT in response to input digital image signals is available.
The color space conversion method using the LUT often uses interpolation calculations together to reduce the memory size of the LUT. The color space conversion of input digital image signals of three colors is implemented using three-dimensional interpolation calculations. Also, the color space conversion of input digital image signals of four colors is implemented using four-dimensional interpolation calculations.
The color space conversion of input digital image signals of three colors, which uses both a three-dimensional lookup table (to be abbreviated as “3D-LUT” hereinafter) and three-dimensional interpolation calculations will be described below.
Details of Color Space Conversion Method
FIG. 12 shows functional blocks that implement color space conversion by three-dimensional interpolation calculations using a 3D-LUT. Using these functional blocks, an interpolated value 1235 can be obtained for input digital image signals (R, G, B) 1205.
For acquiring the interpolated value 1235, the input digital image signals (R, G, B) 1205 are divided into upper signals 1215 and lower signals 1218 by a data division unit 1210. The upper signals 1215 of the three digital image signals are considered as integer coordinates intg_coord of a color space, so as to select a unit solid used in the three-dimensional interpolation calculations.
Unit solids obtained by dividing a color space (RGB space) of a three-dimensional input by a limited value in respective axis directions is shown in reference mark ‘a’ of FIG. 13. In reference mark ‘a’ of FIG. 13, a painted part indicates a unit solid selected by the upper signals 1215 so as to be used in the three-dimensional interpolation calculations.
Note that data after color space conversion corresponding to respective vertices (RD0 to RD7) of a unit solid in reference mark ‘b’ of FIG. 13 are pre-stored in a 3D-LUT 1220 in FIG. 12. These data will be referred to as reference values RD 1225 hereinafter (shown in FIG. 12).
When the reference values RD 1225 corresponding to the respective vertices of the selected unit solid are read out from the 3D-LUT 1220, they are input to an interpolation calculation unit 1230.
On the other hand, the lower signals 1218 of the three digital image signals are considered as fractional coordinates (coordinates of fractional part) frac_coord of the color space, and are used to calculate weighting coefficients (interpolation coefficients) g of the three-dimensional interpolation calculations. In the functional blocks shown in FIG. 12, the fractional coordinates frac_coord themselves are used as the weighting coefficients (interpolation coefficients) g.
The interpolation calculation unit 1230 calculates the interpolated value X 1235 as an output of the functional blocks in FIG. 12 by interpolation calculations (product-sum calculations in most cases) of the reference values RD 1225 and weighting coefficients (interpolation coefficients) g. Interpolation calculation formulas in case of cubic interpolation calculations are as follows (see reference mark ‘b’ of FIG. 13).
equations (1) fi: fractional coordinate frac_coord[i] (i: input axis number)
Si: section width (interval between neighboring reference points RD)
gi: weighting coefficient (interpolation coefficient)
  gi  =      fi    Si  t0=RD0+(RD1−RD0)×g0 t1=RD2+(RD3−RD2)×g0 t2=t0+(t1−t0)×g1 t3=RD4+(RD5−RD4)×g0 t4=RD6+(RD7−RD6)×g0 t5=t3+(t4−t3)×g1 X=t2+(t5−t2)×g2 
Overview of Calculation Methods of Integer Coordinates, Fractional Coordinates, and Weighting Coefficients
As a method of calculating the integer coordinates intg_coord of the color space from the upper signals 1215, and a method of calculating the fractional coordinates frac_coord and weighting coefficients (interpolation coefficients) g from the lower signals 1218 roughly have two different prior arts. The difference between these two prior arts lies in that the reference values RD 1225 present on the respective axes (R, G, B) of the color space shown in reference mark ‘a’ of FIG. 13 are defined by 2M points ((M-th power of 2) points) or 2M+1 points ((M-th power of 2+1) points).
A case wherein the reference values RD 1225 are defined by 2M points will be referred to as prior art 1, a case wherein the reference values RD 1225 are defined by 2M+1 points will be referred to as prior art 2, and these prior arts will be described below. For the sake of simplicity, linear interpolation calculations will be exemplified below in place of three-dimensional interpolation calculations, as shown in reference marks ‘a’ and ‘b’ of FIG. 14. Since the following description is established for each of input axes of N-dimensional interpolation calculations, a description of the linear interpolation calculations suffices.
Calculation Method Using Prior Art 1 (When Reference Values are Defined by 2M Points)
Prior art 1 will be described below using reference mark ‘a’ of FIG. 14. An advantage of prior art 1 is that since 2M points of reference values RD are allocated along an axis, the total number of reference values RD stored in the LUT assumes a value of the power of 2.
In general, the LUT is implemented as a memory. Primarily, since the memory becomes the most efficient circuit when the number of entries assumes a value of the power of 2, hardware of the LUT of prior art 1 can be easily formed, thus providing the advantage of prior art 1. Conversely, prior art 1 suffers the following disadvantage.
When each of the input digital image signals (R, G, B) 1205 is expressed by an input tone P [bits], it has tones ranging from 0 to 2P−1, and a maximum tone is 2P−1. An input digital image signal data_in shown in reference mark ‘a’ of FIG. 14 indicates an input digital image signal corresponding to one axis of the input digital image signals (R, G, B) 1205.
In prior art 1, since the reference values of 2M points are allocated on tones 0 to 2P−1 at nearly equal intervals along the axis, 2M−1 intervals (to be referred to as sections hereinafter) between neighboring reference values RD are formed. The length (section width S) of one section assumes a value obtained by dividing the maximum tone 2P−1 by the number 2M−1 of sections.
As can be understood from reference mark ‘a’ of FIG. 14, if the input digital image signal data_in exists between boundary values 2S and 3S, as shown in reference mark ‘a’ of FIG. 14, reference points required for the linear interpolation calculations are RD[2S] and RD[3S].
An integer coordinate intg_coord of the color space at that time assumes the boundary value 2S, and a fractional coordinate frac_coord of the color space assumes a value obtained by subtracting the boundary value 2S from the input digital image signal data_in (i.e., the remainder of the above division).
With the method of prior art 1, since the number 2M−1 of sections is always an odd value, the integer coordinate intg_coord of the color space cannot be calculated by a simple bit operation. Hence, in prior art 1, in general, the input digital image signal data_in is divided by the section width S, the quotient of the division result is used as an integer coordinate intg_coord of the color space, and the remainder of the division result is used as a fractional coordinate frac_coord of the color space.
For this purpose, prior art 1 requires a divider to calculate the integer coordinate intg_coord and fractional coordinate frac_coord of the color space, which are required for the interpolation calculations.
Also, depending on combinations of a bit depth P [bit] of the input digital image signal data_in and the number 2M of reference values RD of each axis, a problem shown in FIG. 15 is posed.
More specifically, when the maximum tone 2P−1 is divisible by the number 2M−1 of sections (the remainder=‘0’), all sections have an equal section width S. However, when the maximum tone 2P−1 is indivisible by the number 2M−1 of sections, sections having section widths S different from other sections are formed like hatched sections in FIG. 15. For this reason, boundary values and section widths of respective sections must be pre-stored in storage means such as a register or the like, and the input digital image signal data_in must be compared with all boundary values to calculate an integer coordinate intg_coord of the color space based on their comparison result. As a result, this comparison processing with boundary values imposes a heavier calculation load along with increasing the number of reference values of each axis.
Calculation Method Using Prior Art 2 (When Reference Values are Defined by 2M+1 Points)
Prior art 2 will be described below using reference mark ‘b’ of FIG. 14. An advantage of prior art 2 is that no divider is required unlike in prior art 1 above to calculate the integer coordinate intg_coord and fractional coordinate frac_coord of the color space which are required for the interpolation calculations. Another advantage is that no processing for comparing the input digital image signal data_in with all boundary values is required.
As shown in reference mark ‘b’ of FIG. 14, in prior art 2, 2M+1 points of reference values RD are allocated along the axis on tones 0 to 2P−1 at equal intervals. For this reason, the number of intervals (sections) between neighboring reference values RD is 2M. The length (section width S) of one section inevitably assumes a value obtained by dividing the maximum tone 2P−1 by the number 2M of sections. However, an integer coordinate intg_coord of the color space can be calculated by making a right shift calculation of the input digital image signal by P−M bits. At this time, a fractional coordinate frac_coord of the color space is lower P−M bits of the input digital image signal.
Note that the fractional coordinate frac_coord of the color space must be carefully calculated in prior art 2. Since the maximum tone is not 2P but 2P−1, the first (“1”) to “2M−1”-th sections have a section width S of 2P·M. Also, the number of tones of the fractional coordinate frac_coord becomes 2P−M tones. However, the section width S of the last “2M”-th section becomes 2P·M−1, and the number of tones of the fractional coordinate frac_coord becomes 2P−M−1.
For this reason, the fractional coordinate frac_coord of the last “2M”-th section must be adjusted to other sections by multiplying it by 2P·M/(2P·M−1).
In prior art 2, since 2M+1 points of reference values RD are allocated along the axis, the total number of reference values RD stored in the LUT does not assume a value of the power of 2. For this reason, unlike in prior art 1, when the LUT is configured by a memory, it does not become an efficient circuit.
In an N-dimensional interpolation apparatus, the total number of reference values RD required for respective axes is preferably as small as possible since the circuit scale of the LUT exponentially increases with increasing the number N of dimensions of the input digital image signal. The total number of reference value RD of prior art 1 is (2M)N, while that of prior art 2 is (2M+1)N. For this reason, prior art 2 requires a larger circuit scale of the LUT than prior art 1. Also, prior art 1 requires a divider in place of a simple bit shift calculation in prior art 2. However, in a 3- or 4-dimensional interpolation circuit, the circuit scale of the LUT configured by the memory occupies the majority of that of the overall apparatus. For this reason, although the calculation contents are complicated, prior art 1 has a smaller circuit scale.
As described above, prior arts 1 and 2 have opposite advantages and disadvantages. For this reason, when the circuit scale of the LUT is to be reduced, a multi-dimensional interpolation apparatus is implemented by prior art 1. When the calculation processing is to be simplified, a multi-dimensional interpolation apparatus is implemented by prior art 2.